package lab2task2;


/**
 * 
 * @author Bulaev Igor 
 * 
 * Parallel mergesort implementation class
 * 
 * @param values[] - array to be sorted
 * @param aux[] - auxiliary array
 * 
 */

public class MergeSortParallel {

	private int values[];
	private int aux[];

	/**
	 * 
	 * Main sort method
	 * 
	 * @return sorted array
	 * 
	 */

	public int[] sort(int[] values) {
		this.values = values;
		int len = values.length;
		this.aux = new int[len];
		divide(0, len - 1);
		return values;
	}

	private class WorkerRunnable implements Runnable {

		private int low;
		private int high;

		public WorkerRunnable(int low, int high) {
			this.low = low;
			this.high = high;
		}

		@Override
		public void run() {
			divide(low, high);
		}

	}

	/**
	 * 
	 * Division of array method. We launch a new thread on each division of array  
	 * 
	 */
	
	private void divide(int low, int high) {
		if (low < high) {
			int middle = low + (high - low) / 2;			
			Thread rightThread = new Thread(new WorkerRunnable(middle + 1, high));
			rightThread.start();
			divide(low, middle);
			try {			
				rightThread.join();
			} catch (InterruptedException ie) {
				ie.printStackTrace();
			} finally {
				merge(low, middle, high);
			}
		}
	}

	private void merge(int low, int middle, int high) {
		for (int i = low; i <= high; i++) {
			aux[i] = values[i];
		}
		int i = low;
		int j = middle + 1;
		int k = low;
		while (i <= middle && j <= high) {
			if (aux[i] <= aux[j]) {
				values[k] = aux[i];
				i++;
			} else {
				values[k] = aux[j];
				j++;
			}
			k++;
		}
		while (i <= middle) {
			values[k] = aux[i];
			k++;
			i++;
		}
	}
}
